package com.conjane.algo.array_list;

import java.util.Arrays;

public class FindNumberInArray {

    /**
     * 方法一：顺序遍历数组，时间复杂度O(n)
     * @param array
     * @param expectNumber
     * @return
     */
    public static boolean findNumberSequentialSearch(int[] array, int expectNumber){
        for (int i = 0; i < array.length; i++) {
            if (array[i] == expectNumber){
                return true;
            }
        }
        return false;
    }

    /**
     * 方法二：二分搜索，时间复杂度O(logN)
     * @param array
     * @param expectNumber
     * @return
     */
    public static boolean findNumberPartialSearch(int[] array, int expectNumber){
        Arrays.sort(array);
        int left = 0;
        int right = array.length;
        int mid = (left + right) / 2;
        while (left < right){
            if (array[mid] < expectNumber){
                left = mid;
            }else if (array[mid] > expectNumber){
                right = mid;
            }else {
                return true;
            }
            mid = (left + right) / 2;
        }
        return false;
    }

    public static void main(String[] args) {
        int[] array = new int[]{3,4,5,7,4,2,8,9};
        System.out.println(findNumberSequentialSearch(array,1));
        System.out.println(findNumberPartialSearch(array,2));
    }
}
